# coding=utf-8
__author__ = 'st316'
'''
Design and implement a data structure for Least Recently Used (LRU) cache.
It should support the following operations: get and set.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity,
it should invalidate the least recently used item before inserting a new item.
双向queue+dict
'''


class CacheNode:
    def __init__(self, key=None, value=None, pre=None, next_=None):
        self.key = key
        self.value = value
        self.pre = pre
        self.next = next_


class LRUCache:
    # @param capacity, an integer
    def __init__(self, capacity):
        self.capacity = capacity
        self.num = 0
        self.cacheHead = CacheNode(None, 'head')
        self.cacheTail = CacheNode(None, 'tail')
        self.cacheHead.next = self.cacheTail
        self.cacheTail.pre = self.cacheHead
        self.dic = {}

    # @return an integer
    def get(self, key):
        if key in self.dic:
            value = self.dic[key].value
            self.dic[key].pre.next = self.dic[key].next
            self.dic[key].next.pre = self.dic[key].pre
            del self.dic[key]

            # 刪除后重新加至队尾
            self.cacheTail.pre.next = CacheNode(key, value, self.cacheTail.pre, self.cacheTail)
            self.cacheTail.pre = self.cacheTail.pre.next
            self.dic[key] = self.cacheTail.pre

            return value
        else:
            return -1

    # @param key, an integer
    # @param value, an integer
    # @return nothing
    def set(self, key, value):
        if key in self.dic:
            self.dic[key].pre.next = self.dic[key].next
            self.dic[key].next.pre = self.dic[key].pre
            del self.dic[key]
            self.num -= 1
        else:
            if self.num == self.capacity:  # delete the first node
                t = self.cacheHead.next
                t.pre.next = t.next
                t.next.pre = t.pre
                self.dic.pop(t.key)
                del t
                self.num -= 1

        self.cacheTail.pre.next = CacheNode(key, value, self.cacheTail.pre, self.cacheTail)
        self.cacheTail.pre = self.cacheTail.pre.next
        self.dic[key] = self.cacheTail.pre
        self.num += 1


if __name__ == '__main__':
    lcache = LRUCache(1)

    lcache.set(2, 1)
    lcache.get(2)
    lcache.set(3, 2)
    lcache.get(2)
    lcache.get(3)
    lcache.set(48, 261)
    lcache.set(3, 193)
    lcache.set(133, 193)
    lcache.set(60, 183)
    lcache.set(128, 148)
    lcache.set(52, 176)
    lcache.get(48)
    lcache.set(52, 191)
    lcache.set(8, 300)
    lcache.get(136)
    lcache.set(48, 261)
    lcache.set(3, 193)
    lcache.set(133, 193)
    lcache.set(60, 183)
    lcache.set(128, 148)
    lcache.set(52, 176)
    lcache.get(48)
    lcache.set(52, 191)
    lcache.set(8, 300)
    lcache.get(136)
    lcache.set(48, 261)
    lcache.set(3, 193)
    lcache.set(133, 193)
    lcache.set(60, 183)
    lcache.set(128, 148)
    lcache.set(52, 176)
    lcache.get(48)
    lcache.set(52, 191)
    lcache.set(8, 300)
    lcache.get(136)
    lcache.set(48, 261)
    lcache.set(3, 193)
    lcache.set(133, 193)
    lcache.set(60, 183)
    lcache.set(128, 148)
    lcache.set(52, 176)
    lcache.get(48)
    lcache.set(52, 191)
    lcache.set(8, 300)
    lcache.get(136)
    lcache.set(48, 261)
    lcache.set(3, 193)
    lcache.set(133, 193)
    lcache.set(60, 183)
    lcache.set(128, 148)
    lcache.set(52, 176)
    lcache.get(48)
    lcache.set(48, 119)
    lcache.set(10, 241)
    lcache.get(124)
    lcache.set(130, 127)
    lcache.get(61)
    lcache.set(124, 27)
    lcache.get(94)
    lcache.set(29, 304)
    lcache.set(102, 314)
    lcache.get(110)
    lcache.set(23l, 49)
    lcache.set(134, 12)
    lcache.set(55, 90)
    lcache.get(14)
    lcache.get(104)
    lcache.set(77, 165)
    lcache.set(60, 160)
    lcache.get(117)
    lcache.set(58, 30)
    lcache.get(54)
    lcache.get(136)
    lcache.get(128)
    lcache.get(131)
    lcache.set(48, 114)
    lcache.get(136)
    lcache.set(46, 51)
    lcache.set(129, 291)
    lcache.set(96, 207)
    lcache.get(131)
    lcache.set(89, 153)
    lcache.set(120, 154)
    lcache.get(111)
    lcache.get(47)
    lcache.get(5)
    lcache.set(114, 157)
    lcache.set(57, 82)
    lcache.set(113, 106)
    lcache.set(74, 208)
    lcache.get(56)
    lcache.get(59)
    lcache.get(100)
    lcache.get(132)
    lcache.set(127, 202)
    lcache.get(75)
    lcache.set(102, 147)
    lcache.get(37)
    lcache.set(53, 79)
    lcache.set(119, 220)
    lcache.get(47)
    lcache.get(101)
    lcache.get(89)
    lcache.get(20)
    lcache.get(93)
    lcache.get(7)
    lcache.set(48, 109)
    lcache.set(71, 146)
    lcache.get(43)
    lcache.get(122)
    lcache.set(3, 160)
    lcache.get(17)
    lcache.set(80, 22)
    lcache.set(80, 272)
    lcache.get(75)
    lcache.get(117)
    lcache.set(76, 204)
    lcache.set(74, 141)
    lcache.set(107, 93)
    lcache.set(34, 280)
    lcache.set(31, 94)
    lcache.get(132)
    lcache.set(71, 258)
    lcache.get(61)
    lcache.get(60)
    lcache.set(69, 272)
    lcache.get(46)
    lcache.set(42, 264)
    lcache.set(87, 126)
    lcache.set(107, 236)
    lcache.set(131, 218)
    lcache.get(79)
    lcache.set(41, 71)
    lcache.set(94, 111)
    lcache.set(19, 124)
    lcache.set(52, 70)
    lcache.get(131)
    lcache.get(103)
    lcache.get(81)
    lcache.get(126)
    lcache.set(61, 279)
    lcache.set(37, 100)
    lcache.get(95)
    lcache.get(54)
    lcache.set(59, 136)
    lcache.set(101, 219)
    lcache.set(15, 248)
    lcache.set(37, 91)
    lcache.set(11, 174)